/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.vijos;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/4/23
 */
//观光旅游
//学校里面有Ｎ个景点
//两个景点之间可能直接有道路相连，用Dist[I，J]表示它的长度
//每个游客的旅游线路只能是一个回路
// 输入：
//第一行有两个正整数N，M，分别表示学校的景点个数和有多少对景点之间直接有边相连
//以下M行，每行三个正整数，分别表示一条道路的两端的编号，以及这条道路的长度。
// 输出：
//如果该回路存在，则输出一个正整数，表示该回路的总长度；否则输出“No solution.”（不要输出引号）
public class P14_1_1046 {

    public static Object test(int n, int[][] input) {
        List<GraphNode> graphNodes = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graphNodes.add(new GraphNode().setIndex(i + 1));
        }
        for (int i = 0; i < input.length; i++) {
            int[] toInfo = input[i];
            graphNodes.get(toInfo[0] - 1).addTo(graphNodes.get(toInfo[1] - 1), toInfo[2]);
        }
        GraphNode first = graphNodes.get(0);
        List<Router> routers = new ArrayList<>();
        Router router = new Router();
        router.getWalkedNodes().add(first);
        go(first, first, router, routers);
        int minDistance = Integer.MAX_VALUE;
        Router minRouter = null;
        for (Router r : routers) {
            if (r.isSuccess()) {
                if (minDistance > r.getDistance()) {
                    minDistance = r.getDistance();
                    minRouter = r;
                }
            }
        }
        if (minRouter == null) {
            return "No solution";
        } else {
            minRouter.print();
            return minRouter.getDistance();
        }
    }

    public static void go(GraphNode cur, GraphNode first, Router curRouter, List<Router> routers) {
        List<To> tos = cur.getTos();
        for (int i = 0; i < tos.size(); i++) {
            To to = tos.get(i);
            if (to.getTo().getIndex() == first.getIndex()) {
                curRouter.setSuccess(true).setDistance(curRouter.getDistance() + to.getDistance())
                        .getWalkedNodes().add(to.getTo());
                return;
            }
            boolean hasWalked = false;
            for (GraphNode graphNode : curRouter.getWalkedNodes()) {
                if (to.getTo().getIndex() == graphNode.getIndex()) {
                    hasWalked = true;
                }
            }
            if (!hasWalked) {
                Router router = new Router(curRouter);
                routers.add(router);
                router.setDistance(router.getDistance() + to.getDistance())
                        .getWalkedNodes().add(to.getTo());
                go(to.getTo(), first, router, routers);
            }
        }
        routers.remove(curRouter);
    }

    public static class Router {
        private List<GraphNode> walkedNodes = new ArrayList<>();
        private int distance = 0;
        private boolean success = false;

        public void print() {
            StringBuilder sb = new StringBuilder().append('[');
            for (GraphNode graphNode : walkedNodes) {
                sb.append(graphNode.index).append('-');
            }
            System.out.println(sb.substring(0, sb.length() - 1) + ']');
        }

        public boolean isSuccess() {
            return success;
        }

        public Router setSuccess(boolean success) {
            this.success = success;
            return this;
        }

        public Router() {

        }

        public Router(Router other) {
            for (GraphNode graphNode : other.getWalkedNodes()) {
                this.walkedNodes.add(graphNode);
            }
            this.distance = other.getDistance();
        }

        public List<GraphNode> getWalkedNodes() {
            return walkedNodes;
        }

        public Router setWalkedNodes(List<GraphNode> walkedNodes) {
            this.walkedNodes = walkedNodes;
            return this;
        }

        public int getDistance() {
            return distance;
        }

        public Router setDistance(int distance) {
            this.distance = distance;
            return this;
        }
    }

    public static class GraphNode {
        private int index;
        List<To> tos = new ArrayList<>();

        public void addTo(GraphNode to, int distance) {
            this.tos.add(new To().setTo(to).setDistance(distance));
        }

        public int getIndex() {
            return index;
        }

        public GraphNode setIndex(int index) {
            this.index = index;
            return this;
        }

        public List<To> getTos() {
            return tos;
        }

        public GraphNode setTos(List<To> tos) {
            this.tos = tos;
            return this;
        }
    }

    public static class To {
        private GraphNode to;
        private int distance;

        public GraphNode getTo() {
            return to;
        }

        public To setTo(GraphNode to) {
            this.to = to;
            return this;
        }

        public int getDistance() {
            return distance;
        }

        public To setDistance(int distance) {
            this.distance = distance;
            return this;
        }
    }

    public static void main(String[] args) {
        System.out.println(test(5, new int[][] {
                {1, 4, 1},
                {1, 3, 300},
                {3, 1, 10},
                {1, 2, 16},
                {2, 3, 100},
                {2, 5, 15},
                {5, 3, 20}
        }));
        System.out.println(test(4, new int[][] {
                {1, 2, 10},
                {1, 3, 20},
                {1, 4, 30}
        }));
    }
}
